constraint satisfaction

    The process of assigning values to variables while
   meeting certain requirements or "constraints".  For example, in
   graph colouring, a node is a variable, the colour assigned to it
   is its value and a link between two nodes represents the
   constraint that those two nodes must not be assigned the same
   colour.  In scheduling, constraints apply to such variables as
   the starting and ending times for tasks.

   The Simplex method is one well known technique for solving
   numerical constraints.

   The search difficulty of constraint satisfaction problems can be
   determined on average from knowledge of easily computed structural
   properties of the problems.  In fact, hard instances of
   NP-complete problems are concentrated near an abrupt transition
   between under- and over-constrained problems.  This transition is
   analogous to phase transitions in physical systems and offers a
   way to estimate the likely difficulty of a constraint problem
   before attempting to solve it with search.

   <Phase transitions in search> (Tad
   Hogg, XEROX PARC).

   (1995-02-15)